#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 从小到大
void qsort(vector<int> &nums, int left, int right) {
    if (left >= right) return;
    int tmp = nums[left];
    int i = left + 1;
    int j = right;
    while (i < j) {
        while (nums[i] < tmp && j > i) i++;
        while (nums[j] >= tmp && j > i) j--;
        if(i < j) swap(nums[i], nums[j]);
    }
    if(nums[i] < nums[left])
        swap(nums[i], nums[left]);
    qsort(nums, left, i - 1);
    qsort(nums, i, right);
}

// 从大到小
void qsortBig(vector<int>& nums, int left, int right){
    if(left >= right) return;
    cout << "begin, left:" << left << ",right:" << right << "nums[left]:" << nums[left]<< endl;
    int i = left + 1, j = right, tmp = nums[left];
    while(i < j){
        while(i < j && nums[i] >= tmp) i++;
        while(i < j && nums[j] <= tmp) j--;
        cout << "i:" << i << ",nums[i]:" << nums[i] << ",j:" << j << ",nums[j]:" << nums[j] << endl;
        if(i < j) swap(nums[i], nums[j]);
    }
    cout << "nums[i]:" << nums[i] << endl;

    if(nums[i] <= nums[left]){
        swap(nums[left], nums[i - 1]);
    }else{
        swap(nums[left], nums[i]);
    }
    for (auto i : nums) {
        cout << i << ",";
    }
    cout << endl;   
    qsortBig(nums, left, i - 1);
    qsortBig(nums, i, right);
}


int main() {
    vector<int> nums = {187,8559,3718,3741,99,-1,286,1,3,1217, 1531,8056,6,8649,9746};
    for (auto i : nums) {
        cout << i << ",";
    }
    cout << endl;
    qsortBig(nums, 0, nums.size() - 1);
    cout << "sorted:" << endl;
    for (auto i : nums) {
        cout << i << ",";
    }
    cout << endl;
    return 0;
}